package com.linchong.linkedlist.medium;

import com.linchong.linkedlist.basic.BasicLinkList;

/**
 * @author linchong
 * @version 1.0
 * @Date: 2020-11-30 23:25
 * @Description: PartitionList$86. 分隔链表
 * 给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。
 *
 * 你应当保留两个分区中每个节点的初始相对位置。
 *
 *  
 *
 * 示例:
 *
 * 输入: head = 1->4->3->2->5->2, x = 3
 * 输出: 1->2->2->4->3->5
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/partition-list
 *  巧用临时头节点
 *
 *
 */
@SuppressWarnings("unused")
public class PartitionList extends BasicLinkList {

	public ListNode partition(ListNode head, int x) {

		//设置两个临时节点
		ListNode lessHead = new ListNode(0);
		ListNode moreHead = new ListNode(0);
		//对应两个指针指向临时节点
		ListNode lessPtr = lessHead;
		ListNode morePtr = moreHead;

		//遍历链表，按照值的大小，分别放入到不同链表中
		while(head!=null){
			ListNode node = new ListNode(head.val);
			if(head.val<x){
				lessPtr.next = node;
				lessPtr = node;
			}else{
				morePtr.next = node;
				morePtr = node;
			}
			head = head.next;
		}

		//拼接结果
		morePtr.next = null;
		lessPtr.next = moreHead.next;
		return lessHead.next;
	}

}
